In today's data processing, a lot of recognition, prediction, and computation tasks are performed using reference databases used to characterize input data. Depending upon the problem to be solved, these reference databases contain patterns that are sub-images, sub-signals, subsets of data, and combinations thereof. The patterns that are stored in these reference databases are referred to herein below as prototypes. As known by those skilled in the art, these patterns are generally represented by a vector, which is an array in an n-dimensional space.
Well-known methods for characterizing unknown patterns, referred to herein as input patterns, using reference databases are based upon input space mapping algorithms. Such algorithms include K-Nearest-Neighbor (KNN) or the Region Of Influence (ROI) algorithms. The base principle of these algorithms is to compute a distance between an input pattern and each of the stored prototypes in order to find the closest pattern(s), which usually depends on predetermined thresholds. U.S. Pat. No. 5,621,863, entitled “Neuron Circuit,” issued Apr. 15, 1997 to Boulet et al., assigned to IBM Corp., and incorporated by reference herein, describes artificial neural networks based on input space mapping algorithms that include innovative elementary processors of a new type, referred to as the ZISC neurons (ZISC is a registered trade mark of IBM Corp.). An essential characteristic of the ZISC neurons lies in their ability to work in parallel, which that, when an input pattern is presented to the ANN, all ZISC neurons compute the distance between the input pattern and their stored prototypes at the same time. Thus, the ZISC ANN response time regarding the totality of the distance evaluation process is constant whatever the number of prototypes, unlike the response time of a software emulation of such a process, which linearly depends upon the number of prototypes.
FIG. 1 illustrates the basic hardware that will be used to illustrate the distance evaluation technique as it is currently practiced to date in a ZISC ANN. Now turning to FIG. 1, the architecture of a neural system 100 is shown. Neural system 100 comprises a host computer 110, e.g., a personal computer, and a conventional ZISC ANN 120 that includes a plurality of neurons 130-1 to 130-n (generically referenced as 130 hereinafter). Physically, the ANN 120 can consist of a printed circuit board having a few ZISC chips, e.g., ZISCO36 chips which include 36 neurons each, mounted thereon. Each neuron, e.g. 130-1, is schematically reduced in FIG. 1 to two essential elements for the sake of simplicity: a prototype memory 140-1 (collectively, 140) dedicated to store a prototype, when the neuron has learned an input vector during the learning phase, and a distance evaluator 150-1 (collectively, 150). Data-in bus 160 sequentially applies the set of components of an input pattern to all neurons 130 of the ANN 120 in parallel and data-out bus 170 transmits the results of the distance evaluation process, typically the distance and the category (and other or more specified parameters could be envisioned as well) to the host 110. As taught in the above in U.S. Pat. No. 5,621,863, when an input pattern is fed into each neuron 130 through data bus 160, it is compared in the distance evaluator 150 with the prototype stored therein, so that the result generally consists of a pair of values: a distance and the category. For the sake of simplicity, the category register is not shown in FIG. 1; instead, it is considered to be included in the distance evaluator 150. As apparent in FIG. 1, the ZISC ANN architecture is such that all the distance evaluations are simultaneously performed in all the neurons composing the ANN.
The conventional ANN 120 depicted in FIG. 1 is limited to the storage of a fixed number of prototypes, as determined by the number, n, of neurons. In this case, the number of prototypes p is such that p<=n. However, depending upon several factors like the number, m, of prototype components and the required accuracy of the ANN 120, modern real-time applications may use from a few thousand to several hundreds of thousands of ZISC neurons. It is not always realistic to use as many ZISC neurons as it would be required. Even with the dramatic increase of the level of integration that has been achieved in recent years, which permits integration of millions of transistors on a single piece of semiconductor, just a few hundred neurons can be embedded in a silicon chip. This, in turn, would allow an integration of a few thousand neurons on one large printed circuit board. As a result, it would be quite complex and expensive to build an ANN physically composed of several hundreds of thousands of neurons.
There is, thus, a real need to implement a ZISC ANN that could process as many prototypes as necessary without requiring complex and thus expensive hardware, in order to meet present and future real time applications. It is accordingly a major aim of the method and circuits of the present invention to remedy the limitations and shortcomings of the FIG. 1 conventional ANN architecture that are recited above.